1. Field of the Invention
This invention relates to branch prediction mechanisms for microprocessors. More specifically to a branch prediction mechanism that stores "speculative history" when a branch prediction is made such that branch history is immediately available for branch instructions within small loops.
2. Art Background
Early microprocessors generally processed instructions one at a time. Each instruction was processed using four sequential stages: instruction fetch, instruction decode, execute, and result writeback. Within such microprocessors, different dedicated logic blocks performed each different processing stage. Each logic block waits until all the previous logic blocks complete operations before beginning its operation.
To improve efficiency, microprocessor designers overlapped the operations of the fetch, decode, execute, and writeback stages such that the microprocessor operated on several instructions simultaneously. In operation, the fetch, decode, execute, and writeback stages concurrently process different instructions. At each clock tick the results of each processing stage are passed to the following processing stage. Microprocessors that use the technique of overlapping the fetch, decode, execute, and writeback stages are known as "pipelined" microprocessors.
In order for a pipelined microprocessor to operate efficiently, an instruction fetch unit at the head of the pipeline must continually provide the pipeline with a stream of instructions. However, conditional branch instructions within an instruction stream prevent an instruction fetch unit at the head of a pipeline from fetching the correct instructions until the condition is resolved. Since the condition will not be resolved until further down the pipeline, the instruction fetch unit cannot fetch the proper instructions.
To alleviate this problem, many pipelined microprocessors use branch prediction mechanisms that predict the outcome of branch instructions, and then fetch subsequent instructions according to the branch prediction. For example, Yeh & Patt introduced a highly accurate two-level branch prediction mechanism. (See Tse Yu Yeh and Yale N. Patt, Two-Level Adaptive Branch Prediction., The 24th ACM/IEEE International Symposium and Workshop on Microarchitecture, November 1991, pp. 51-61) When the branch prediction mechanism mispredicts a branch, the instructions which should not have been fetched are flushed out of the instruction pipeline.
Most branch prediction mechanisms, such as the two-level branch prediction mechanism disclosed by Yeh & Patt, operate by dynamically maintaining the outcome history of branches. The branch predictions are then made based upon the stored branch history.
When a small loop is executing in a deeply pipelined processor, several occurrences of the same branch instruction can be in the instruction pipeline at the same time. In such a situation, the earlier branches are unresolved. Therefore, no history for the earlier branches will be available to the branch prediction mechanism. Since the branch history for the branch instructions farther down the pipeline is not available to the later occurrences of the branch instruction, the branch predictions for the later branch instruction will be made using outdated history. Therefore, in a deeply pipelined processor, a branch prediction mechanism that makes predictions based upon branch history often mispredicts branches in small loops.